perm filename HSII.PUB[X,ALS]1 blob
sn#069827 filedate 1973-11-05 generic text, type T, neo UTF8
00100 .<< revised: 1200 22 Oct 73 >>
00200
00300 .device xgp
00400 .require "xcribl.dfs[a700pu00]" source
00500 .macro ttl(what)⊂if lines <7 then next page; skip 2;
00600 . once center;
00700 ↓%what%↓
00800 . break;
00900 .⊃
01000 .macro lttl(what)⊂if lines<6 then next page; skip 2;
01100 . once flush left;
01200 ↓%what%↓
01300 . break;
01400 .⊃
01500 .macro plttl(what)⊂if lines<6 then next page; skip 2;
01600 . once flush left;
01700 what
01800 . break;
01900 .⊃
02000 .retain
02100 .macro h⊂⊃
02200 .footsep←"__________________";
02300 .count footnote inline from 1 to 9 in page printing
02400 . ⊂"*********"[1 to footnote]⊃;
02500 .at "$$" entry "*"
02600 .⊂ next footnote; !;
02700 . send foot
02800 . ⊂ turn on "{"; preface 1;
02900 . spread←1; indent 0,3; turn on "#";
03000 {!⎇#entry
03100 . break
03200 . ⊃
03300 .⊃
03400 .akset←"ngr25.kst[a730ks00]";bkset←"ngb25.kst[a730ks00]";
03500 .font a "ngr25.kst[a730ks00]";font b "ngb25.kst[a730ks00]";
03600 .xstart; xseta(7); xsetb(11); xwaita; xwaitb; xend;
03700 .macro dent ⊂ start indent 3,3,3; end; ⊃
03800 .indent 8,0
03900 .turn on "\{↓_%#α";
04000 .at "[[" entry "]" ⊂⎇%bentry%a{⊃ <<****this is n.g.****>>
04100 .retain; preface 1;
00100 .page frame 55 high 80 wide
00200 .group skip 20
00300 .begin center
00400 %BHEARSAY II%A
00500
00600 Description
00700 and
00800 Specification
00900
01000
01100 Department of Computer Science
01200 Carnegie-Mellon University
01300
01400 {date⎇
01500 .end
01600 .page←0
01700 .next page
01800 .every heading(Hearsay II,,{date⎇)
01900 .every footing(,{page⎇,)
02000 .nofill
02100
02200
02300
02400 %bDESCRIPTION OF HSII%a
02500
02600
02700 ↓_Introduction_↓
02800
02900 HSII (Hearsay II) is the proposed next version for a speech
03000 understanding system at CMU. Its design is a direct outgrowth of
03100 experience with the Hearsay system. The design of HSII differs from
03200 the Hearsay system in the following significant ways:
03300
03400 1. The Hearsay system consists of a ↓_few large_↓ knowledge
03500 sources (i.e., three), whereas HSII consists of a ↓_large_↓
03600 number of ↓_small_↓ knowledge sources (i.e., 60-100).
03700
03800 2. The knowledge sources of Hearsay share information only at
03900 the ↓_word level_↓, whereas the knowledge sources of HSII
04000 cooperate at ↓_various levels_↓ of data (i.e., phonetic,
04100 phonemic, word, etc.). The various data levels of HSII are
04200 represented by a lattice-type information structure.
04300
04400 3. The knowledge sources of Hearsay are activated in a ↓_lockstep_↓
04500 manner based on the hypothesis-test paradigm, whereas the
04600 knowledge sources of HSII are activated in an ↓_asynchronous_↓,
04700 data-directed manner where the action of hypothesizing-testing
04800 is not embodied in one knowledge source but rather subdivided
04900 among a group of knowledge sources. In addition, there are
05000 knowledge sources which refine a hypothesis, propagate the
05100 effects of hypotheses from one level to another level, and
05200 delete hypotheses which are no longer interesting.
05300
05400 4. In the Hearsay system, data generated from the validation of
05500 a hypothesis is not available for the validation of other
05600 hypotheses, whereas in HSII this information can, if
05700 desired, be retained.
05800
05900 In addition to these differences in system design between Hearsay and
06000 HSII, HSII is intended to be eventually implemented on loosely-coupled
06100 (ARPA NET) and closely-coupled (C.mmp) multiprocessor systems.
06200
06300 ↓_The Global Data Base_↓
06400
06500 The design of HSII is centered around a global data base (blackboard)
06600 which is accessible to all knowledge sources. The global data base is
06700 structured as a lattice-like data structure. There are several levels
06800 in the lattice (concepts, phrases, words, syllables, phonemics,
06900 phonetics, subphonetics, acoustic parameters), where each level has
07000 the same elemental data structure except for the primitive information
07100 unit stored at the level (i.e., words, phonemes, etc.). The structure
07200 is lattice-like because there may be more than one type of primitive
07300 information unit at a given level (e.g., the phonemic level may
07400 contain both phone labels and VFS labels used as support for the
07500 next higher level).
07600
07700 The primitive information unit of each level in the lattice
07800 can be thought of as an abstraction (a grouping) of the primitive
07900 information units held in the lower level. The information held at
08000 each level is correlated with a particular time period in the speech
08100 utterance and represents a ↓_hypothesis_↓ about this time period.
08200 The data structure permits the representation of alternative hypotheses
08300 within a time interval as well as permitting hypotheses that represent
08400 overlapping time intervals. A sequence in time of these hypotheses can
08500 be grouped together as a single alternative hypothesis covering a
08600 larger time interval, and a set of alternative hypotheses for a
08700 particular time range can be grouped together into a single
08800 hypothesis (e.g., suppose at the phonemic level there are two
08900 possible hypotheses for a particular time period, but they both fall
09000 into the vowel class; then you could form a hypothesis that this
09100 particular time period is a vowel which could be one of two possible
09200 phones). In addition, a hypothesis can contain contextual assumptions
09300 which define when it is valid. These contextual assumptions are
09400 represented in terms of hypotheses with associated time ranges outside
09500 of the particular time period of the hypothesis in question, which
09600 assumptions must be true in order for the hypothesis in question to be
09700 true.
09800
09900 Hypotheses at different levels in the lattice are related through
10000 ↓_links_↓. Links serve as hypothesis interconnection points,
10100 providing storage for contextual abstractions formed about the link's
10200 lower hypothesis. There are four types of relationships that links
10300 can be used to construct among hypotheses:
10400
10500 1. a sequence in time of hypotheses at one level can be used
10600 to support (validate) a hypothesis at a higher level
10700
10800 2. alternative hypotheses covering the same time interval can be
10900 used to support a single higher level hypothesis
11000
11100 3. non-temporal sequences (AND condition) of hypotheses at one
11200 level can be used to support a higher level hypothesis
11300
11400 4. non-temporal alternative hypotheses (OR condition) can be used
11500 to support a higher level hypothesis.
11600
11700 The alternative ↓_uses_↓ of a hypothesis by a higher level
11800 hypothesis are related to the alternative ↓_supports_↓ of that
11900 hypothesis by lower hypotheses through the use of a ↓_connection matrix_↓.
12000 In particular, the use of a hypothesis implies certain contextual
12100 assumptions about its environment, while the support of hypotheses
12200 may itself be predicated on a particular set of contextual assumptions.
12300 The connection matrix contains which alternative supports of a hypothesis
12400 are valid with which alternative uses of that hypothesis.
12500
12600 ↓_Hypothesis Structure_↓
12700
12800 Each hypothesis contains the following information:
12900
13000 1. the level in the lattice where the hypothesis was made and
13100 the lexicon associated with this hypothesis
13200
13300 2. the primitive information unit which represents the hypothesis
13400 (defined and accessed relative to the lexicon associated with
13500 the hypothesis)
13600
13700 3. the begin/end time ranges defining where the hypothesis is
13800 valid
13900
14000 4. the support connections of the hypothesis: which higher level
14100 hypothesis it provides support for; which lower level hypotheses
14200 it receives support from; the method of lower level support (e.g.,
14300 a set of alternatives, or a sequence in time which may include
14400 contextual assumptions); and the connection matrix between the
14500 hypotheses which receive support with those alternatives that
14600 provide support
14700
14800 5. the processing state of the hypothesis consisting of:
14900
15000 a. whether the hypothesis has been initialized, verified,
15100 rejected or guaranteed
15200
15300 b. whether the hypothesis has been rated
15400
15500 c. whether the hypothesis has been supported
15600
15700 d. whether the hypothesis has been used to support
15800 another hypothesis
15900
16000 e. whether all support links of the hypothesis are
16100 connected to at least one use of the hypothesis
16200 (state of connection matrix)
16300
16400 f. whether the hypothesis is currently being examined
16500 or modified (synchronization)
16600
16700 g. whether the hypothesis is available for precondition
16800 evaluation
16900
17000 6. the scheduling parameters for the hypothesis:
17100 the current rating for the validity of the hypothesis and an
17200 associated weighting, an effort measure indicating how
17300 much time has been spent validating the hypothesis, and
17400 an attention focus (priority) on how important it is to work
17500 on that hypothesis
17600
17700 7. the data state of the hypothesis:
17800 a set of attribute-value pairs which represent knowledge
17900 specific to the hypothesis; these attribute-value pairs are
18000 added, modified or deleted by the particular knowledge sources
18100 that have operated on this hypothesis.
18200
18300 ↓_Link Structure_↓
18400
18500 Each link contains the following information:
18600
18700 1. begin/end time ranges
18800
18900 2. `support' connections: upper hypothesis and lower hypothesis
19000
19100 3. processing state:
19200
19300 a. whether the link has been rated
19400
19500 b. whether the link is currently begin examined or
19600 modified (synchronization)
19700
19800 4. scheduling parameters:
19900 current rating with weighting (i.e., how important the
20000 rating is in constructing a composite rating for the
20100 lower hypothesis); effort measure; and attention focus
20200 (request for computation)
20300
20400 The link duplicates some of the same type of information held in a
20500 hypothesis. However, the information held in a hypothesis represents
20600 a composite which does not distinguish among the particular connections
20700 of lower level links to upper level links. In addition, by duplicating
20800 the information in the links, the recomputation of hypothesis parameters
20900 are made easier when new links are added or old links removed.
21000
21100 ↓_Knowledge Source Invocation_↓
21200
21300 Upon being introduced into the system, a knowledge source specifies
21400 what conditions in the global data structure must be true for the
21500 knowledge source to be invoked. The set of hypotheses that satisfy the
21600 condition is the context within which the knowledge source begins working.
21700 If there are multiple places in the data base that satisfy the unspecified
21800 conditions, the knowledge source can be invoked sequentially for each
21900 place in the data base, can be separately instantiated for each place
22000 so that it can parallel process, or can be invoked with the list of
22100 all places in the data base currently satisfying the condition.
22200
22300 A knowledge source specifies its precondition for invocation by
22400 specifying a series of hypotheses masks and relationships among these
22500 masks. A hypothesis mask is a partial description of a hypothesis,
22600 where the values of its components may be specified in terms of a don't-
22700 care condition, a range of values, or based on the values of components
22800 of a hypothesis which matched another hypothesis mask. For example,
22900 in this latter case, the set of hypotheses that supported a hypothesis
23000 matched by another mask can be specified as the set of hypotheses that
23100 will be examined for candidates to match another hypothesis mask. A
23200 complex precondition can then be specified in terms of an and/or tree
23300 of hypothesis masks together with component value relationships among
23400 these masks (or a procedure which has the effect of evaluating
23500 such an and/or tree).
23600
23700 An alternative method of knowledge source invocation, and that
23800 used in a preliminary version of HSII, is to define a set of pre-
23900 condition procedures whose duty it is to monitor modifications made
24000 to the data base. The procedures may then make arbitrarily complex
24100 decisions (based on current and past modifications to the data base)
24200 resulting in the activation of desired knowledge sources within the
24300 chosen contexts. The differences between the two approaches to knowledge
24400 source invocation lie in who is responsible for specifying, evaluating,
24500 and acting upon the various precondition structures.
24600
24700
24800 .next page
24900 %bHYPOTHESIS AND LINK EXAMINATION%a
25000
25100 ↓_Hypothesis Examination_↓
25200
25300 Given a reference (itemvar or item in SAIL) to a hypothesis
25400 (HYP), the following functions examine the hypothesis structure:
25500
25600 1. LEVEL(HYP) - returns an integer number; hypotheses between
25700 levels are by convention given the level number of the
25800 lower level. Possible level names (in descending order):
25900 SEMANTIC!LEVEL,SYNTACTIC!LEVEL, WORD!LEVEL, SYLLABIC!LEVEL,
26000 PHONEMIC!LEVEL, PHONETIC!LEVEL, SUBPHONETIC!LEVEL,
26100 ACOUSTIC!LEVEL.
26200
26300 2. HYPOTHESIS(HYP) - returns the primitive information unit
26400 associated with HYP. The type of the result is dependent
26500 upon the lexicon accesses and is presumed to be
26600 known by the caller. The hypothesis actually contains two
26700 more elementary pieces of information which are used to
26800 retrieve the final information unit:
26900
27000 a. LEXICON(HYP) - integer identifier for lexicon
27100 associated with HYP.
27200
27300 b. HYPOTHESIS!INDEX(HYP) - integer index into lexicon
27400 used in retrieval of primitive information unit.
27600
27700 A lexicon accessing routine is established for each
27800 lexicon to be used and may be arbitrarily complex (or
27900 simple). The lexicon contents may be either static or
28000 dynamic in nature and are established by routines written
28100 for each lexicon.
28200
28300 3. Begin/End Time Ranges
28400
28500 BEGIN!TIME(HYP) - returns an integer value representing
28600 the mid-point of the begin time range
28700
28800 BEGIN!RANGE(HYP) - returns an integer value representing
28900 the fuzziness of the BEGIN!TIME in + and - directions
29000
29100 END!TIME(HYP) - returns an integer value representing
29200 the mid-point of the end time range
29300
29400 END!RANGE(HYP) - returns an integer value representing
29500 the fuzziness of the END!TIME
29600
29700 .if lines < 6 then next page;
29800 4. Support Relationships*
29900 .footsep ←"------------------"
30000 .send foot ⊂
30100 *Always return LINK - but possibly HYP should be returned, easier for
30200 RETRIEVAL mechanism.
30300 .⊃
30400 SUPPORT!TO(HYP) - returns a set of LINK references
30500 that specify the hypotheses that are supported by
30600 this hypothesis; no associated type
30700
30750 SUPPORT!FROM(HYP) - returns a set of link references
30755 which specify the hypotheses that supports this
30760 hypothesis
30765
30800 SUPPORT!FROM!TYPE(HYP) - returns an integer value
30900 indicating the type of support relationship (which
31000 may be taken as the type of HYP):
31100
31200 a. NO!SUPPORT:
31205
31210 SUPPORT!FROM(HYP) returns a null list
31215
31220 b. DIRECT:
31225
31230 return a one element list
31232
31235 c. OPTION:
31500 the set of LINK references specify
31600 alternative support hypotheses covering
31700 the time interval of HYP
31800
32700 d. SEQUENCE:
32800
33000 the temporally-ordered list of LINKS
33100 are used to support HYP in a temporally
33200 sequential manner
33300
33400 e. CONTEXT:
33500 the temporally-ordered list of LINKS
33600 with time ranges outside the time range
33700 of HYP but all must be true if the given
33800 support is valid
33900
34000 f. OR:
34100
34300 the set of LINK references that specify
34305 alternative support hypotheses that do not
34310 necessarily overlap temporally
34600
34700 g. AND:
34800
35000 the set of LINKS whose logical conjunction
35005 supports HYP
35300
35305 4.5 Connections
35310
35315 If SUPPORT!FROM!TYPE(HYP) is OPTION or OR,
35320 it is possible to specify which alternative links
35325 from below support which hypotheses above.
35330
35335 UPPER!CONNECTION(HYP,LINKLOWER)
35340
35345 returns the subset of SUPPORT!TO links
35350 which are supported by LINKLOWER via HYP
35355
35360 LOWER!CONNECTION(HYP<LINKUPPER)
35365
35370 returns the subset of SUPPORT!FROM links
35375 any of which will support LINKUPPER via HYP
35380
35400 5. Processing state
35500
35600 HYPOTHESIS!STATE(HYP)
35700
35800 NULL - null
35900 UNVERIFIED - initialized but unverified
36000 VERIFIED - verified
36100 REJECTED - rejected
36200 GUARANTEED - guaranteed
36300
36400 RATING!STATE(HYP)
36500
36600 UNRATED - no rating
36700 RATED - rated
36800
36900 SUPPORT!TO!STATE(HYP)
37000
37100 UNUSED - no uses of hypothesis
37200 USED - uses of hypothesis
37300
37400 SUPPORT!FROM!STATE(HYP)
37500
37600 UNSUPPORTED - hypothesis unsupported
37700 PARTIALLY!SUPPORTED - hypothesis partially
37800 supported (incomplete temporal sequence
37900 specification)
38000 SUPPORTED - hypothesis completely supported
38005 UNCHECKED - hypothesis not checked for completeness
38010 of support
38100
38200 CONNECTION!STATE(HYP)
38300
38305 NO!CONNECTION
38400 INCOMPLETE - unconnected LINKS
38500 (incompleted paths through connection matrix)
38600 COMPLETE - all LINKS connected
38700 to at least one other LINK via a path
38800 through connection matrix
38900
39000 SYNCH!STATE(HYP)
39100
39200 FREE - no modification currently
39300 MODIFYING - currently being modified
39400 EXAMINING - currently being examined
39500 (multiple knowledge sources may simultaneously
39600 examine hypothesis)
39700
39800 .if lines < 7 then next page;
39900 ACTIVITY!STATE(HYP)
40000
40100 INACTIVE - not to be used for precondition
40200 testing
40300 ACTIVE - ok to be used for precondition
40400 testing
40500
40600 6. Scheduling Parameters
40700
40800 RATING(HYP) - returns a integer (represents current
40900 validity of hypothesis)
41000
41100 WEIGHTING(HYP) - returns a integer (represents quality
41200 of rating or a rating interval range)
41300
41400 EFFORT(HYP) - returns a integer (represents how
41500 much processing time has been expended in validating
41600 hypothesis)
41700
41800 FOCUS(HYP) - returns a integer (represents
41900 how much interest there is in validating hypothesis:
42000 a request for computation)
42100
42200 7. Data State - consisting of attribute/value pairs, where
42300 each attribute has associated with it an accessing (interpretation)
42400 function which produces the stored data item given the
42500 index value stored in the association (in much the same
42600 manner as the primitive information unit of a hypothesis
42700 is retrieved by the appropriate lexicon accessing function,
42800 given the hypothesis index stored in the data base).
42900
43000 ATTRIBUTE!VALUE(HYP,ATTRIBUTE) - returns stored data
43100 item, where ATTRIBUTE is an item or itemvar denoting
43200 an accessing routine. The type of the result is dependent
43300 upon the attribute and is presumed to be known by the
43400 caller.
43500
43600 ↓_Link Examination_↓
43700
43800 Given a reference (item or itemvar) to a LINK, the following
43900 functions examine a LINK:
44000
44100 LINK!BEGIN!TIME(LINK)
44200 LINK!BEGIN!RANGE(LINK)
44300 LINK!END!TIME(LINK)
44400 LINK!END!RANGE(LINK)
44500 HYP!UPPER(LINK) - returns a hypothesis reference to upper hypothesis
44600 HYP!LOWER(LINK) - returns a hypothesis reference to lower hypothesis
44700 HYP!UPPER!TYPE(LINK) - one of OPTION!SUPPORT, SEQUENCE!SUPPORT,
44800 CONTEXT!SUPPORT, OR!SUPPORT, or AND!SUPPORT
44900 HYP!LOWER!TYPE(LINK) - as above
45000 LINK!TYPE(LINK) - equivalent to HYP!UPPER!TYPE(LINK)
45100 LINK!RATING!STATE(LINK) - LINK!NOT!RATED or LINK!RATED
45200 LINK!SYNCH!STATE(LINK) - SYNCH!FREE, SYNCH!MODIFYING, or
45300 SYNCH!EXAMINING
45400 LINK!RATING(LINK)
45500 LINK!WEIGHTING(LINK)
45600 LINK!EFFORT(LINK)
45700 LINK!FOCUS(LINK)
45800
45900 .next page
46000 %bHYPOTHESIS AND LINK MODIFICATION%a
46100
46200 ↓_Hypothesis Modification_↓
46300
46400 A hypothesis HYP may be modified by only one knowledge source at
46500 a time, and this knowledge source is explicitly specified in the
46600 process of extracting the hypothesis from the global data base.
46700
46800 When a hypothesis is reentered into the data base, all the changes
46900 that have been made in the hypothesis are signalled to the precondition
47000 evaluation mechanism. In addition, the particular type of modification
47100 (support added, deleted, etc.) and its effect on a hypothesis are
47200 recorded. This information is then available to a precondition evaluation
47300 procedure so that a knowledge source can be invoked and provided with
47400 both the hypotheses that satisfied the precondition together with the
47500 particular modifications to those hypotheses that caused the precondition
47600 to be satisfied.
47700
47800 The type of possible modifications to a hypothesis are classified
47900 according to various categories, each of which represents the set of
48000 HYP references satisfying the indicated condition during the preceding
48100 time instant. Also given are routines for retrieving the actual changes
48200 performed on a given HYP:
48300
48400
48500 .begin tabs 10,15,42,50
48600 \\↓_SET_↓\\↓_ROUTINE_↓
48700
48800 HYPOTHESIS!INDEX!CHANGED!HYPS\\(NONE)
48900
49000 TIME!RANGE!CHANGED!HYPS\\(NONE - SUPERSET)
49100 \BEGIN!TIME!CHANGED!HYPS\OLD!BEGIN!TIME(HYP)
49200 \BEGIN!RANGE!CHANGED!HYPS\OLD!BEGIN!RANGE(HYP)
49300 \END!TIME!CHANGED!HYPS\OLD!END!TIME(HYP)
49400 \END!RANGE!CHANGED!HYPS\OLD!END!RANGE(HYP)
49500
49600 SUPPORT!TO!CHANGED!HYPS\\(NONE - SUPERSET)
49700 \SUPPORT!TO!ADDED!HYPS\SUPPORT!TO!ADDED(HYP) - gives link ref's
49800 \SUPPORT!TO!MODIFIED!HYPS\SUPPORT!TO!MODIFIED(HYP)
49900 \SUPPORT!TO!DELETED!HYPS\SUPPORT!TO!DELETED(HYP)
50000
50100 SUPPORT!FROM!CHANGED!HYPS\\(NONE - SUPERSET)
50200 \SUPPORT!FROM!ADDED!HYPS\SUPPORT!FROM!ADDED(HYP) - gives link ref's
50300 \SUPPORT!FROM!MODIFIED!HYPS\SUPPORT!FROM!MODIFIED(HYP)
50400 \SUPPORT!FROM!DELETED!HYPS\SUPPORT!FROM!DELETED(HYP)
50500
50600 CONNECTION!CHANGED!HYPS\\(NONE - SUPERSET)
50700 \CONNECTION!ADDED!HYPS\CONNECTION!ADDED(HYP) - gives link pairs
50800 \CONNECTION!DELETED!HYPS\CONNECTION!DELETED(HYP)
50900
51000 PROCESSING!STATE!CHANGED!HYPS\\(NONE - SUPERSET)
51100 \HYPOTHESIS!STATE!CHANGED!HYPS\OLD!HYPOTHESIS!STATE(HYP) - gives integer
51200 \RATING!STATE!CHANGED!HYPS
51300 \SUPPORT!TO!STATE!CHANGED!HYPS\OLD!SUPPORT!TO!STATE(HYP)
51400 \SUPPORT!FROM!STATE!CHANGED!HYPS\OLD!SUPPORT!FROM!STATE(HYP)
51500 \CONNECTION!STATE!CHANGED!HYPS\OLD!CONNECTION!STATE(HYP)
51600 \SYNCH!STATE!CHANGED!HYPS
51700 \ACTIVITY!STATE!CHANGED!HYPS
51800
51900 SCHEDULING!PARMS!CHANGED!HYPS\\(NONE - SUPERSET)
52000 \RATING!CHANGED!HYPS\OLD!RATING(HYP) - gives integer
52100 \WEIGHTING!CHANGED!HYPS\OLD!WEIGHTING(HYP)
52200 \EFFORT!CHANGED!HYPS\OLD!EFFORT(HYP)
52300 \FOCUS!CHANGED!HYPS\OLD!FOCUS(HYP)
52400
52500 DATA!STATE!CHANGED!HYPS\DATA!STATE!CHANGE(HYP) - gives set
52600 \\\of ATTRIBUTE ref's whose
52700 \\\old values may be accessed
52800 \\\by OLD!ATTRIBUTE!VALUE(HYP,
52900 \\\ATTRIBUTE)
53000 .end
53100
53200 Note - Corresponding modification sets for links are TIME!RANGE!CHANGED!LINKS,
53300 PROCESSING!STATE!CHANGED!LINKS, and SCHEDULING!PARMS!CHANGED!LINKS with
53400 obvious substitutions of `LINK' for `HYP' throughout.
53500
53600 Given a reference HYP to a hypothesis, the various modifications
53700 that may be performed are:
53800
53900 1. Level number/lexicon identifier
54000
54100 No modification allowed after initial creation
54200
54300 2. Hypothesis Datum (defined in terms of a lexicon identifier
54400 and a hypothesis index)
54500
54600 DEFINE!HYPOTHESIS!INDEX(HYP, integer)
54700
54800 where the integer index for the datum is generated by a lookup
54900 routine associated with the desired lexicon.
55000
55100 Side effects:
55200
55250 OLD!HYPOTHESIS!STATE(HYP)=HYPOTHESIS!STATE(HYP)
55300 HYPOTHESIS!STATE(HYP) = HYP!STATE!UNVERIFIED
55400 Add HYP to HYPOTHESIS!STATE!CHANGED!HYPS
55500
55600 3. Begin/End Time Ranges
55700
55800 DEFINE!BEGIN!TIME(HYP, integer)
55900 DEFINE!BEGIN!RANGE(HYP, integer)
56000 DEFINE!END!TIME(HYP, integer)
56100 DEFINE!END!RANGE(HYP, integer)
56200
56300 Side effects:
56400
56500 Add HYP to APPROPRIATE TIME!RANGE!CHANGED!HYPS subset
56600
56700 4. Support Relationships (Link Creation and Deletion)
56800
56900 a. ESTABLISH!SUPPORT!TO(HYP, HYPUPPER, TYPE)
57000 where TYPE is one of OPTION!SUPPORT, SEQUENCE!SUPPORT,
57100 CONTEXT!SUPPORT, OR!SUPPORT, or AND!SUPPORT (specifying
57200 TYPE may be superfluous since both HYP's are typed).
57300 This creates a LINK between HYP and HYPUPPER, and returns
57400 a reference to this LINK. LINK is then initialized by
57500 other routines.
57600
57700 Side effects:
57800
57900 Add LINK to SUPPORT!TO(HYP)
58000 Add LINK to SUPPORT!FROM(HYPUPPER)
58600 Add HYP to SUPPORT!TO!ADDED!HYPS
58605 and SUPPORT!TO!CHANGED!HYPS
58700 Add HYPUPPER to SUPPORT!FROM!ADDED!HYPS.
58705 and SUPPORT!FROM!CHANGED!HYPS
58800
58900 b. ESTABLISH!SUPPORT!FROM(HYP, HYPLOWER, TYPE)
59000 is equivalent to
59100 ESTABLISH!SUPPORT!TO(HYPLOWER, HYP, TYPE)
59200
59300 c. ESTABLISH!CONNECTION(HYP, LINKLOWER, LINKUPPER) -
59400 establish connection between LINKLOWER that supports
59500 HYP and LINKUPPER that is supported by HYP.
59600
59700 Side effects:
59800
60200 Add HYP to CONNECTION!ADDED!HYPS
60205 and CONNECTION!CHANGED!HYPS
60300 Add LINKLOWER to CONNECTIONS!ADDED!LOWER(HYP)
60305 Add LINKUPPER to CONNECTIONS!ADDED!UPPER(HYP)
60400
60500 d. DELETE!SUPPORT!TO(HYP, HYPUPPER) - delete LINK connecting
60600 HYP to HYPUPPER.
60700
60800 Side effects:
60900
61000 Remove LINK from SUPPORT!TO(HYP)
61100 Remove LINK from SUPPORT!FROM(HYPUPPER)
61700 Add HYP to SUPPORT!TO!DELETED!HYPS
61705 and SUPPORT!TO!CHANGED!HYPS
61800 Add HYPUPPER to SUPPORT!FROM!DELETED!HYPS
61805 and SUPPORT!FROM!CHANGED!HYPS
61900
62000 If any connections associated with LINK:
62100 Remove all such connections and
62200 add LINKLOWER to CONNECTIONS!DELETED!LOWER(HYP)
62205 add LINKUPPER to CONNECTIONS!DELETED!UPPER(HYP)
62400 Add HYP to CONNECTION!DELETED!HYPS
62405 and CONNECTION!CHANGED!HYPS
62500
62600 e. DELETE!SUPPORT!FROM(HYP, HYPLOWER)
62700 is equivalent to
62800 DELETE!SUPPORT!TO(HYPLOWER,HYP)
62900
63000 f. DELETE!CONNECTION(HYP, LINKLOWER, LINKUPPER) -
63100 remove the connection between LINKLOWER that supports
63200 HYP and LINKUPPER that is supported by HYP.
63300
63400 Side effects:
63500
63600 Remove (LINKLOWER, LINKUPPER) from CONNECTION!MATRIX
63900 Add HYP to CONNECTION!DELETED!HYPS
64000 Add (LINKLOWER, LINKUPPER) to CONNECTION!DELETED(HYP)
64100
64200 5. Processing State
64300
64305 these states are set by other routines
64400 DEFINE!HYPOTHESIS!STATE(HYP, integer)
64500 DEFINE!RATING!STATE(HYP, integer)
64600 DEFINE!SUPPORT!TO!STATE(HYP, integer)
64700 DEFINE!SUPPORT!FROM!STATE(HYP, integer)
64800 DEFINE!CONNECTION!STATE(HYP, integer)
64900 DEFINE!SYNCH!STATE(HYP, integer)
65000 DEFINE!ACTIVITY!STATE(HYP, integer)
65100
65200 Side effects:
65300
65400 Add HYP to appropriate PROCESSING!STATE!CHANGED!HYPS subset
65500
65600 6. Scheduling Parameters
65700
65800 DEFINE!RATING(HYP, integer)
65900 DEFINE!WEIGHTING(HYP, integer)
66000 DEFINE!EFFORT(HYP, integer)
66100 DEFINE!FOCUS(HYP, integer)
66200
66300 Side effects:
66400
66500 Add HYP to appropriate SCHEDULING!PARMS!CHANGED!HYPS subset
66600
66700 7. Data State
66800
66900 ESTABLISH!ATTRIBUTE!VALUE(HYP, ATTRIBUTE, VALUE) - establish
67000 ATTRIBUTE/VALUE pair, whose ATTRIBUTE is an item denoting
67100 accessing routine and the type of VALUE is appropriate to
67200 ATTRIBUTE.
67300
67400 DELETE!ATTRIBUTE(HYP, ATTRIBUTE)
67500
67600 Side effects:
67700
67800 Add HYP to DATA!STATE!CHANGED!HYPS
67900
68000 ↓_Link Modification_↓
68100
68200 Given a reference LINK to a link, the various modifications that
68300 may be performed are:
68400
68500 1. Link Begin/End Time Ranges
68600
68700 DEFINE!LINK!BEGIN!TIME(LINK, integer)
68800 DEFINE!LINK!BEGIN!RANGE(LINK, integer)
68900 DEFINE!LINK!END!TIME(LINK, integer)
69000 DEFINE!LINK!END!RANGE(LINK, integer)
69100
69200 Side effects:
69300
69400 Add LINK to appropriate TIME!RANGE!CHANGED!LINKS subset
69500
69600 2. Link Processing State
69700
69800 DEFINE!LINK!RATING!STATE(LINK, integer)
69900 DEFINE!LINK!SYNCH!STATE(LINK, integer)
70000
70100 Side effects:
70200
70300 Add LINK to appropriate PROCESSING!STATE!CHANGED!LINKS subset
70400
70500 3. Link Scheduling Parameters
70600
70700 DEFINE!LINK!RATING(LINK, integer)
70800 DEFINE!LINK!WEIGHTING(LINK, integer)
70900 DEFINE!LINK!EFFORT(LINK, integer)
71000 DEFINE!LINK!FOCUS(LINK, integer)
71100
71200 Side effects:
71300
71400 Add LINK to appropriate SCHEDULING!PARMS!CHANGED!LINKS subset
71500
71600 Note: For any link modification:
71700
71800 Add HYP!UPPER(LINK) to SUPPORT!FROM!MODIFIED!HYPS
71900 Add HYP!LOWER(LINK) to SUPPORT!TO!MODIFIED!HYPS
72000
72100 .next page
72200 %bHYPOTHESIS MANIPULATION%a
72300
72400 ↓_Hypothesis Creation_↓
72500
72600 CREATE!HYP(Knowledge-source, Level-number, Lexicon, Begin-time,
72700 Begin-range, End-time, End-range)
72800
72900 This routine returns a reference HYP to a newly created hypothesis.
73000 Hypothesis characteristics:
73100
73200 LEVEL(HYP) = Level-number
73300 LEXICON(HYP) = Lexicon
73400 HYPOTHESIS!INDEX(HYP) = 0
73500 BEGIN!TIME(HYP) = Begin-time
73600 BEGIN!RANGE(HYP) = Begin-range
73700 END!TIME(HYP) = End-time
73800 END!RANGE(HYP) = End-range
73900 SUPPORT!TO(HYP) = PHI
74000 SUPPORT!FROM!TYPE(HYP) = NO!SUPPORT
74100 HYPOTHESIS!STATE(HYP) = NULL
74200 RATING!STATE(HYP) = UNRATED
74300 SUPPORT!TO!STATE(HYP) = UNUSED
74400 SUPPORT!FROM!STATE(HYP) = UNSUPPORTED
74500 CONNECTION!STATE(HYP) = INCOMPLETE
74600 SYNCH!STATE(HYP) = MODIFYING
74700 ACTIVITY!STATE(HYP) = INACTIVE
74800 Scheduling parameters not set
74900 Data state empty
75000
75100 ↓_Hypothesis Accessing_↓
75200
75300 EXTRACT!HYP(Knowledge-source, HYPS, Wait)
75400
75500 This operation permits Knowledge-source to examine and modify any
75600 of the hypotheses specified, where HYPS is a set of hypothesis references.
75700
75800 Any change made on an extracted hypothesis will not be entered
75900 into the data base for precondition testing until the INSERT!HYP operation
76000 is performed on the extracted hypothesis.
76100
76200 If Wait = TRUE, the EXTRACT!HYP will not return until all the
76300 hypotheses in HYPS are available for extraction; if Wait = FALSE, the
76400 subset of HYPS that can be immediately extracted will be returned by
76500 the function. A hypothesis is available for extraction if its SYNCH!STATE =
76600 SYNCH!FREE. Extracted hypotheses have their SYNCH!STATE set to SYNCH!MODIFYING.
76700
76800
76900 EXAMINE!HYP(Knowledge-source, HYPS, Wait)
77000
77100 This operation allows multiple read-only access to the hypotheses
77200 in the set HYPS. The Wait parameter works as for EXTRACT!HYP. A
77300 hypothesis is available for examination if its SYNCH!STATE = SYNCH!FREE.
77400 Hypotheses under examination have their SYNCH!STATE set to SYNCH!EXAMINING.
77500
77600
77700 INSERT!HYP(Knowledge-source, HYPS)
77800
77900 This operation reenters the hypotheses of the set HYPS back into
78000 the global data base, allowing the hypotheses to be accessed by some
78100 other knowledge source. The SYNCH!STATE of all hypotheses in HYPS is
78200 set to SYNCH!FREE.
78300
78400 ↓_Hypothesis Deletion_↓
78500
78600 DELETE!HYP(Knowledge-source, HYPS)
78700
78800 This operation removes the hypotheses of HYPS from the global
78900 data base.
79000
79100 Hypothesis deletion has the following side effects:
79200
79300 FOREACH HYPUPPER supported by HYP ε HYPS DO
79400 DELETE!SUPPORT!TO(HYP, HYPUPPER);
79500 FOREACH HYPLOWER supporting HYP ε HYPS DO
79600 DELETE!SUPPORT!FROM(HYP, HYPLOWER);
79700
79800
79900 .next page
80000 %bASSOCIATIVE RETRIEVAL%a
80100
80200 As part of the kernel of HSII, primitives are provided for
80300 associatively searching the data base for hypotheses satisfying specified
80400 conditions (e.g., finding all hypotheses which contain a vowel within
80500 a certain time range). The search condition is specified by a hypothesis
80600 ↓_mask_↓, which is an incomplete specification of the components
80700 of a hypothesis. This incomplete specification permits a component to
80800 be a don't-care condition or a set of values. The resultant hypothesis
80900 mask can then be matched against a list of hypotheses; the set of
81000 hypotheses whose compnent vales fall within the set of values specified
81100 by the hypothesis mask are then returned as the result of the search.
81200
81300 The following operations are provided for mask manipulation:
81400
81500 1. CREATE!MASK(MSK) - returns a reference to a hypothesis mask
81600 which has been initialized to MSK (or to don't-care conditions
81700 if MSK = 0).
81800
81900 2. DELETE!MASK(MSK) - Delete all data storage associated with
82000 the given hypothesis mask.
82100
82200 3. Specifying Mask Constraints - For each component of a hypothesis,
82300 a set of alternative match conditions may be built up by
82400 repeatedly invoking the routine (specified below) that enables
82500 the hypothesis mask for that particular match component. The
82600 component specifiers:
82700
82800 MASK!LEVEL(MSK, lower, upper) - lower/upper specify a range
82900 of integer values
83000 MASK!LEXICON(MSK, integer)
83100 MASK!HYPOTHESIS!INDEX(MSK, integer)
83200 MASK!SUPPORT!TO(MSK, LINK!LIST) - defines a condition
83300 which is true if every LINK ε LINK!LIST is contained
83400 in SUPPORT!TO(HYP). If LINK!LIST is empty, then always
83500 match.
83600 MASK!ALTERNATIVE!SUPPORT!FROM(MSK, LINK!LIST)
83700 MASK!SEQUENCE!SUPPORT!FROM(MSK, LINK!LIST)
83800 MASK!CONTEXT!SUPPORT!FROM(MSK, LINK!LIST)
83900 MASK!OR!SUPPORT!FROM(MSK, LINK!LIST)
84000 MASK!AND!SUPPORT!FROM(MSK, LINK!LIST)
84100 MASK!CONNECTION(MSK, LINK!LOWER, LINK!UPPER)
84200 MASK!HYPOTHESIS!STATE(MSK, integer)
84300 MASK!RATING!STATE(MSK, integer)
84400 MASK!SUPPORT!TO!STATE(MSK, integer)
84500 MASK!SUPPORT!TO!ADDED!STATE(MSK, Boolean)
84600 MASK!SUPPORT!TO!MODIFIED!STATE(MSK, Boolean)
84700 MASK!SUPPORT!TO!DELETED!STATE(MSK, Boolean)
84800 (analogous conditions for SUPPORT!FROM)
84900 MASK!SYNCH!STATE(MSK, integer)
85000 MASK!RATING(MSK, real-lower, real-upper)
85100 MASK!DATA!STATE(MSK, ATTRIBUTE, VALUE)
85200
85300 4. RETRIEVE!OR(HYP!LIST, MSK!LIST, Extract, Wait)
85400 RETRIEVE!AND(HYP!LIST, MSK!LIST, Extract, Wait)
85500
85600 Given a list of potential hypotheses and a list of masks,
85700 these routines return those hypotheses which match any
85800 of the masks or all of them, respectively. The extract Boolean
85900 indicates whether the hypotheses that succeed in matching will
86000 also be extracted from the data base. If TRUE, the Wait Boolean
86100 will suspend the search if any hypothesis in HYP!LIST is not
86200 currently examinable and wait until it is before resuming the
86300 search; if FALSE, any non-examinable hypothesis is simply
86400 ignored.
86500
86600 .next page
86700 %bPRECONDITION STRUCTURE%a
86800
86900 As a first pass at precondition monitoring, each knwoledge source
87000 will specify its preconditions in terms of a procedure. This procedure
87100 will be resumed whenever sufficient changes have been made to the
87200 global data base. The procedure will have the responsibility for
87300 creating instantiations of its associated knowledge source with the
87400 correct parameters whenever the need arises. A precondition will be
87500 specified in a procedural manner in terms of a sequence of RETRIEVE
87600 operations.
87700
87800 If a precondition procedure needs to hold state between resumptions
87900 of activity, it may store this information as part of the data state
88000 of the hypotheses that it is interested in considering at its next
88100 reactivation. In addition, a precondition procedure will have access
88200 to the following global data structures:
88300
88400 ALL!HYPS - the set of all active hypotheses
88500 CHANGED!HYPS - the set of all hypotheses that have just changed
88600 on this cycle.
88700
88800 There are also separate subsets which discriminate among various
88900 classes of data structure alterations (see previous section on
89000 Hypothesis Modification). In addition, for each hypothesis
89100 in each of these subsets, the actual change that occurred is recorded
89200 and is accessible.